#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <SeqQueue.h>
#include "mgraph.h"

#define VERY_BIG 6666


	static int get_xb(vertex *gh,char v,int len)
{
	int i;
	for(i = 0;i < len;i++)
	{
		if(v == gh[i].data)
			return i;
	}
	return -1;
}

int len;
	void graph_create()
{
	int k,start,stop;
	char arr[Max] = {0};
	printf("输入顶点数组\n");
	scanf("%s%*c",arr);
	len = strlen(arr);
	for(k = 0;k < len;k++)
	{
		gh[k].data = arr[k];
		gh[k].first = NULL;
		gh[k].last = NULL;
	}
		printf("输入关系集\n");
	while(1)
	{
		bian *newnode = NULL;
		newnode = malloc(sizeof(*newnode));
		newnode->stop_index = 0;
		newnode->w = 0;
		newnode->next = NULL;
		
		vextype s,p;
		int w;
		scanf("%c%c%d%*c",&s,&p,&w);

		if(s == '#')
				break;
		start = get_xb(gh,s,len);
		stop = get_xb(gh,p,len);
		newnode->stop_index = stop;
		newnode->w = w;
	
		if((gh[start].first) == NULL)
		{
			gh[start].first = newnode;
		}	
		else
		{
			gh[start].last->next = newnode;
		}
			gh[start].last = newnode;
	}
}

	void print_graph(vertex *graph)
{
	int v;
	for(v = 0;v < len;v++)
	{
		bian *p = graph[v].first;
		printf("%d->",v);
		while(p->next != NULL)
		{
			printf("%d->",p->stop_index);
			p = p->next;
		}
		printf("%d\n",p->stop_index);	
	}
	printf("\n");
}

	int visited[Max];


	static void DFS(vertex *graph,int v0)
{
	printf("%c ",graph[v0].data);
	visited[v0] = 1;
	
	bian *p = graph[v0].first;
	while(p != NULL)
	{
		if(visited[p->stop_index] != 1)
		{
			DFS(graph,p->stop_index);
		}
		p = p->next;
	}	

}

	void DFSTRAVER(vertex *graph)
{
	int i;
	for(i = 0;i < len;i++)
	{
		visited[i] = 0;
	}
	for(i = 0;i < len;i++)
	{
		if(visited[i] != 1)
		DFS(graph,i);
	}
}


static void graph_BFS(vertex *graph,int v0)
{

		queue_head *que = NULL;
		que = Init_Queue();
//入队第一个元素
		EnQueue(que,graph[v0].data);
//队列不为空时循环出队，每出队一个元素，将这个元素的所有有效边入队
		while(!IsEmpty_Queue(que))
		{
				Datatype receive;
				DeQueue(que,&receive);
					printf("%c ",receive);
					bian *p = graph[v0].first;

				while(p)
				{
					if(visited[p->stop_index] == 0)
					{
						visited[p->stop_index] = 1;	
						EnQueue(que,graph[p->stop_index].data);
					}
					p = p->next;
				}

		}
		Destroy_Queue(&que);

}

	void BFSTRAVER(vertex *graph)
{
	int i;
	for(i = 0;i < len;i++)
	{
		visited[i] = 0;
	}
	for(i = 0;i < len;i++)
	{
		if(visited[i] != 1)
		{
			graph_BFS(graph,i);
		}
	}
	
}

int s[Max];
int dist[Max];
char path[Max][Max];

void Dijkstra(vertex *graph,int v0)
{
		int i,j;
		for(i = 0;i < len;i++)
		{
				s[i] = 0;
				dist[i] = VERY_BIG;
				bian *p = graph[v0].first;
				while(p)
				{
						if(p->stop_index == i)
						{
								dist[i] = p->w;
								break;
						}	
						p = p->next;
				}

				memset(path[i],'\0',Max);
				path[i][0] = graph[v0].data;
				path[i][1] = graph[i].data;
		}
		s[v0] = 1;

		int n = 0;
		while(++n < len)
		{
		int u,min_vaule = VERY_BIG;
				for(i = 0;i < len;i++)
				{
						if(s[i] == 0)
						{
								if(dist[i] < min_vaule)
								{
										min_vaule = dist[i];
										u = i;
								}
						}
				}
				s[u] = 1;
				for(i = 0;i < len;i++)
				{
				int u_i = VERY_BIG;
						if(s[i] == 0)
						{
								bian *p = NULL;
								p = graph[u].first;
								while(p)
								{
										if(p->stop_index == i)
										{
												u_i = p->w;
												break;
										}	
										p = p->next;
								}
								//u_i等于very_big时证明u到i没有直接路径
								if(dist[u] + u_i < dist[i] && u_i != VERY_BIG)
								{
										dist[i] = dist[u] + u_i;
										strcpy(path[i],path[u]);
										path[i][strlen(path[i])] = graph[i].data;
								}
						}
				}
		}
		for(i = 0;i < len;i++)
		{
			if(i == v0)
			{
				continue;
			}
			printf("%c->%c [%d] ",graph[v0].data,graph[i].data,dist[i]);
			for(j = 0;j < strlen(path[i])-1;j++)
			{
				printf("%c->",path[i][j]);
			}
			printf("%c\n",path[i][j]);
		}
}
